/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.array

import junit.framework.TestCase.assertEquals
import org.jheaps.AddressableHeap
import org.jheaps.Heap
import org.jheaps.array.BinaryArrayAddressableHeap.Companion.heapify
import org.jheaps.array.DaryArrayAddressableHeap.Companion.heapify
import org.jheaps.array.DaryArrayHeap.Companion.heapify
import org.junit.Assert
import org.junit.BeforeClass
import org.junit.Test
import java.util.*

class HeapifyTest {
    @Test
    fun testHeapifySort() {
        val generator = Random(1)

        val classes = 8

        val a = arrayOfNulls<Int>(SIZE)
        for (i in 0 until SIZE) {
            a[i] = generator.nextInt()
        }

        val h = java.lang.reflect.Array.newInstance(Heap::class.java, classes) as Array<Heap<Int?>>

        h[0] = BinaryArrayHeap.heapify(a)
        h[1] = heapify(2, a)
        h[2] = heapify(3, a)
        h[3] = heapify(4, a)
        h[4] = heapify(5, a)
        h[5] = BinaryArrayWeakHeap.heapify(a)
        h[6] = BinaryArrayBulkInsertWeakHeap.heapify(a)
        h[7] = MinMaxBinaryArrayDoubleEndedHeap.heapify(a)

        var elements = SIZE
        var prev: Int? = null
        var cur: Int?
        while (elements > 0) {
            cur = h[0].findMin()
            for (i in 1 until classes) {
                Assert.assertEquals(cur!!.toLong(), h[i].findMin()!!.toLong())
            }
            for (i in 0 until classes) {
                h[i].deleteMin()
            }
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur!!) <= 0)
            }
            prev = cur
            elements--
        }
    }

    @Test
    fun testHeapifySortWithComparator() {
        val generator = Random(1)

        val classes = 8

        val a = arrayOfNulls<Int>(SIZE)
        for (i in 0 until SIZE) {
            a[i] = generator.nextInt()
        }

        val h = java.lang.reflect.Array.newInstance(Heap::class.java, classes) as Array<Heap<Int?>>

        h[0] = BinaryArrayHeap.heapify(a, comparator)
        h[1] = heapify(2, a, comparator)
        h[2] = heapify(3, a, comparator)
        h[3] = heapify(4, a, comparator)
        h[4] = heapify(5, a, comparator)
        h[5] = BinaryArrayWeakHeap.heapify(a, comparator)
        h[6] = BinaryArrayBulkInsertWeakHeap.heapify(a, comparator)
        h[7] = MinMaxBinaryArrayDoubleEndedHeap.heapify(a, comparator)

        var elements = SIZE
        var prev: Int? = null
        var cur: Int?
        while (elements > 0) {
            cur = h[0].findMin()
            for (i in 1 until classes) {
                Assert.assertEquals(cur!!.toLong(), h[i].findMin()!!.toLong())
            }
            for (i in 0 until classes) {
                h[i].deleteMin()
            }
            if (prev != null) {
                Assert.assertTrue(comparator!!.compare(prev, cur) <= 0)
            }
            prev = cur
            elements--
        }
    }

    @Test
    fun testHeapifyZeroLengthArray() {
        val a = arrayOfNulls<Int>(0)

        val nonfixed = 8

        val h = java.lang.reflect.Array.newInstance(Heap::class.java, nonfixed) as Array<Heap<Int?>>

        h[0] = BinaryArrayHeap.heapify(a)
        h[1] = heapify(2, a)
        h[2] = heapify(3, a)
        h[3] = heapify(4, a)
        h[4] = heapify(5, a)
        h[5] = BinaryArrayWeakHeap.heapify(a)
        h[6] = BinaryArrayBulkInsertWeakHeap.heapify(a)
        h[7] = MinMaxBinaryArrayDoubleEndedHeap.heapify(a)

        for (i in 0 until nonfixed) {
            Assert.assertTrue(h[i].isEmpty)
            try {
                h[i].insert(1)
            } catch (e: IllegalStateException) {
                Assert.fail("No!")
            }
        }
    }

    @Test
    fun testHeapifyZeroLengthArrayComparator() {
        val a = arrayOfNulls<Int>(0)

        val nonfixed = 8

        val h = java.lang.reflect.Array.newInstance(Heap::class.java, nonfixed) as Array<Heap<Int?>>

        h[0] = BinaryArrayHeap.heapify(a, comparator)
        h[1] = heapify(2, a, comparator)
        h[2] = heapify(3, a, comparator)
        h[3] = heapify(4, a, comparator)
        h[4] = heapify(5, a, comparator)
        h[5] = BinaryArrayWeakHeap.heapify(a, comparator)
        h[6] = BinaryArrayBulkInsertWeakHeap.heapify(a, comparator)
        h[7] = MinMaxBinaryArrayDoubleEndedHeap.heapify(a, comparator)

        for (i in 0 until nonfixed) {
            Assert.assertTrue(h[i].isEmpty)
            try {
                h[i].insert(1)
            } catch (e: IllegalStateException) {
                Assert.fail("No!")
            }
        }
    }

    @Test
    fun testHeapifyZeroLengthArray1() {
        val a = arrayOfNulls<Int>(0)

        val classes = 4

        val h = java.lang.reflect.Array
            .newInstance(AddressableHeap::class.java, classes) as Array<AddressableHeap<Int?, String>>

        h[0] = BinaryArrayAddressableHeap.heapify(a, null)
        h[1] = DaryArrayAddressableHeap.heapify(3, a, null)
        h[2] = DaryArrayAddressableHeap.heapify(4, a, null)
        h[3] = DaryArrayAddressableHeap.heapify(5, a, null)

        for (i in 0 until classes) {
            Assert.assertTrue(h[i].isEmpty)
            try {
                assertEquals(1, h[i].insert(1).key)
            } catch (e: IllegalStateException) {
                Assert.fail("No!")
            }
        }
    }

    @Test
    fun testHeapifyZeroLengthArray2() {
        val a = arrayOfNulls<Int>(0)

        val classes = 4

        val h = java.lang.reflect.Array
            .newInstance(AddressableHeap::class.java, classes) as Array<AddressableHeap<Int?, String>>
        h[0] = BinaryArrayAddressableHeap.heapify(a, null)
        h[1] = DaryArrayAddressableHeap.heapify(3, a, null)
        h[2] = DaryArrayAddressableHeap.heapify(4, a, null)
        h[3] = DaryArrayAddressableHeap.heapify(5, a, null)

        for (i in 0 until classes) {
            h[i].insert(1)
            h[i].insert(2)
            h[i].insert(3)
            h[i].insert(4)
            Assert.assertEquals(4, h[i].size())
        }
    }

    @Test
    fun testHeapifyZeroLengthArrayComparator1() {
        val a = arrayOfNulls<Int>(0)

        val classes = 4

        val h = java.lang.reflect.Array
            .newInstance(AddressableHeap::class.java, classes) as Array<AddressableHeap<Int?, String>>
        h[0] = heapify(a, null, comparator)
        h[1] = heapify(3, a, null, comparator)
        h[2] = heapify(4, a, null, comparator)
        h[3] = heapify(5, a, null, comparator)

        for (i in 0 until classes) {
            Assert.assertTrue(h[i].isEmpty)
            try {
                assertEquals(1, h[i].insert(1).key)
            } catch (e: IllegalStateException) {
                Assert.fail("No!")
            }
        }
    }

    @Test
    fun testHeapifyBadParameters() {
        val a = arrayOfNulls<Int>(0)

        try {
            BinaryArrayHeap.heapify<Any>(null)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

       /* try {
            BinaryArrayHeap.heapify<Any>(null, comparator)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }*/

        try {
            heapify(1, a)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        try {
            heapify(1, a, comparator)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        /*try {
            heapify<Any>(2, null)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        try {
            DaryArrayHeap.heapify<Any>(2, null, comparator)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }*/

        try {
            heapify<Any, Any>(null, null)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        /*try {
            BinaryArrayAddressableHeap.heapify<Any, Any>(null, null, comparator)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }*/

        try {
            heapify(arrayOfNulls<Int>(2), arrayOfNulls<Int>(3))
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        try {
            heapify(arrayOfNulls<Int>(2), arrayOfNulls<Int>(3), comparator)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        try {
            heapify(1, arrayOfNulls<Int>(2), arrayOfNulls<Int>(2))
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        try {
            heapify<Any, Int?>(3, null, arrayOfNulls(2))
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        try {
            heapify(3, arrayOfNulls<Int>(3), arrayOfNulls<Int>(2))
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        try {
            heapify(1, arrayOfNulls<Int>(2), arrayOfNulls<Int>(2), comparator)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        /*try {
            heapify<Any, Int?>(3, null, arrayOfNulls(2), comparator)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }*/

        try {
            heapify(3, arrayOfNulls<Int>(3), arrayOfNulls<Int>(2), comparator)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        /*try {
            BinaryArrayWeakHeap.heapify<Any>(null)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }*/

        /*try {
            BinaryArrayWeakHeap.heapify<Int>(null, comparator)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }*/

        try {
            BinaryArrayBulkInsertWeakHeap.heapify<Any>(null)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        try {
            BinaryArrayBulkInsertWeakHeap.heapify<Int>(null, comparator)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        /*try {
            MinMaxBinaryArrayDoubleEndedHeap.heapify<Any>(null)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }

        try {
            MinMaxBinaryArrayDoubleEndedHeap.heapify<Any>(null, comparator)
            Assert.fail("No!")
        } catch (ignored: IllegalArgumentException) {
        }*/
    }

    @Test
    fun testArrayAddressableHeapifySort() {
        val generator = Random(1)

        val a = arrayOfNulls<Int>(SIZE)
        for (i in 0 until SIZE) {
            a[i] = generator.nextInt()
        }

        val classes = 4

        val h = java.lang.reflect.Array
            .newInstance(AddressableHeap::class.java, classes) as Array<AddressableHeap<Int?, String>>
        h[0] = BinaryArrayAddressableHeap.heapify(a, null)
        h[1] = DaryArrayAddressableHeap.heapify(3, a, null)
        h[2] = DaryArrayAddressableHeap.heapify(4, a, null)
        h[3] = DaryArrayAddressableHeap.heapify(5, a, null)

        var elements = SIZE
        val prev = arrayOfNulls<Int>(classes)
        val cur = arrayOfNulls<Int>(classes)
        while (elements > 0) {
            for (i in 0 until classes) {
                cur[i] = h[i].findMin().key
                if (i > 0) {
                    Assert.assertEquals(cur[0], cur[i])
                }
            }
            for (i in 0 until classes) {
                h[i].deleteMin()
            }
            for (i in 0 until classes) {
                if (prev[i] != null) {
                    Assert.assertTrue(prev[i]!!.compareTo(cur[i]!!) <= 0)
                }
                prev[i] = cur[i]
            }
            elements--
        }
    }

    @Test
    fun testArrayAddressableHeapifySortWithValues() {
        val generator = Random(1)

        val a = arrayOfNulls<Int>(SIZE)
        val b = arrayOfNulls<String>(SIZE)
        for (i in 0 until SIZE) {
            a[i] = generator.nextInt()
            b[i] = a[i].toString()
        }

        val classes = 4

        val h = java.lang.reflect.Array
            .newInstance(AddressableHeap::class.java, classes) as Array<AddressableHeap<Int?, String?>>
        h[0] = heapify(a, b)
        h[1] = heapify(3, a, b)
        h[2] = heapify(4, a, b)
        h[3] = heapify(5, a, b)

        var elements = SIZE
        val prev = arrayOfNulls<Int>(classes)
        val cur = arrayOfNulls<Int>(classes)
        while (elements > 0) {
            for (i in 0 until classes) {
                cur[i] = h[i].findMin().key
                assertEquals(h[i].findMin().value, h[i].findMin().key.toString())
                if (i > 0) {
                    Assert.assertEquals(cur[0], cur[i])
                }
            }
            for (i in 0 until classes) {
                h[i].deleteMin()
            }
            for (i in 0 until classes) {
                if (prev[i] != null) {
                    Assert.assertTrue(prev[i]!!.compareTo(cur[i]!!) <= 0)
                }
                prev[i] = cur[i]
            }
            elements--
        }
    }

    @Test
    fun testArrayAddressableHeapifySortComparator() {
        val generator = Random(1)

        val a = arrayOfNulls<Int>(SIZE)
        for (i in 0 until SIZE) {
            a[i] = generator.nextInt()
        }

        val classes = 4

        val h = java.lang.reflect.Array
            .newInstance(AddressableHeap::class.java, classes) as Array<AddressableHeap<Int?, String>>
        h[0] = heapify(a, null, comparator)
        h[1] = heapify(3, a, null, comparator)
        h[2] = heapify(4, a, null, comparator)
        h[3] = heapify(5, a, null, comparator)

        var elements = SIZE
        val prev = arrayOfNulls<Int>(classes)
        val cur = arrayOfNulls<Int>(classes)
        while (elements > 0) {
            for (i in 0 until classes) {
                cur[i] = h[i].findMin().key
                if (i > 0) {
                    Assert.assertEquals(cur[0], cur[i])
                }
            }
            for (i in 0 until classes) {
                h[i].deleteMin()
            }
            for (i in 0 until classes) {
                if (prev[i] != null) {
                    Assert.assertTrue(comparator!!.compare(prev[i], cur[i]) <= 0)
                }
                prev[i] = cur[i]
            }
            elements--
        }
    }

    @Test
    fun testArrayAddressableHeapifySortComparatorWithValues() {
        val generator = Random(1)

        val a = arrayOfNulls<Int>(SIZE)
        val b = arrayOfNulls<String>(SIZE)
        for (i in 0 until SIZE) {
            a[i] = generator.nextInt()
            b[i] = a[i].toString()
        }

        val classes = 4

        val h = java.lang.reflect.Array
            .newInstance(AddressableHeap::class.java, classes) as Array<AddressableHeap<Int?, String?>>
        h[0] = heapify(a, b, comparator)
        h[1] = heapify(3, a, b, comparator)
        h[2] = heapify(4, a, b, comparator)
        h[3] = heapify(5, a, b, comparator)

        var elements = SIZE
        val prev = arrayOfNulls<Int>(classes)
        val cur = arrayOfNulls<Int>(classes)
        while (elements > 0) {
            for (i in 0 until classes) {
                cur[i] = h[i].findMin().key
                assertEquals(h[i].findMin().value, h[i].findMin().key.toString())
                if (i > 0) {
                    Assert.assertEquals(cur[0], cur[i])
                }
            }
            for (i in 0 until classes) {
                h[i].deleteMin()
            }
            for (i in 0 until classes) {
                if (prev[i] != null) {
                    Assert.assertTrue(comparator!!.compare(prev[i], cur[i]) <= 0)
                }
                prev[i] = cur[i]
            }
            elements--
        }
    }

    companion object {
        private const val SIZE = 100000

        private var comparator: Comparator<Int?>? = null

        @JvmStatic
        @BeforeClass
        fun setUpClass(): Unit {
            comparator = Comparator { o1, o2 ->
                if (o1!! < o2!!) {
                    1
                } else if (o1 > o2) {
                    -1
                } else {
                    0
                }
            }
        }
    }
}
